import java.io.BufferedInputStream;
import java.io.InputStream;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;

/**
 * Optimizer reads in context data from file, determines the best sequence
 * of contexts to split data sets, then writes the results into a file.
 * 
 * @author Yong Shin
 *
 */
public abstract class Optimizer {

	/** Enable debug spew */
    protected boolean DEBUG = false;
    protected boolean FULLDEBUG = true; // FULLDEBUG = print everything. 
    //  nonfullDEBUG == print only important things. 
    
        /** sets DEBUG to (x > 0)  */
        public void setDebugFlag(int x) { 
           DEBUG = (x>0); 
           FULLDEBUG = (x==1);
        }
	
	/** Comments start with this character */
	private static final char COMMENT = '#';
	
	/** Default context characteristics definition file name */
	public static final String DEFAULT_CCD = "default.ccd";
	
	/** Default context characteristics data file name */
	public static final String DEFAULT_CC = "default.cc";
	
	/** Default context tree description file name */
	public static final String DEFAULT_CTD = "default.ctd";

	/** Default optimizer class name */
	public static final String DEFAULT_OPTNAME = "GreedyOptimizer";
	
	/** Stores context characteristics data */
	protected ContextDataCollection contextData;

	
	/**
	 * Recursively labels the context tree nodes in in-order traversal.
	 * @param node
	 * @param order order of the node
	 * @return
	 */
	private int labelContextTreeNode(ContextTreeNode node, int order) {
		ContextTreeNode left = node.getLeftChild();
		ContextTreeNode right = node.getRightChild();
		if (left != null) {
			order = labelContextTreeNode(left, order);
		}
		node.setLabel(order);
		order++;
		if (right != null) {
			order = labelContextTreeNode(right, order);
		}
		return order;
	}
	
	/**
	 * Recursively writes the context tree nodes in pre-order traversal.
	 * @param node
	 * @return number of nodes written
	 * @throws IOException 
	 */
	private int writeContextTreeNode(BufferedWriter w, ContextTreeNode node) throws IOException {
		int count = 0;
		ContextTreeNode left = node.getLeftChild();
		ContextTreeNode right = node.getRightChild();
		
		if (left != null && right != null) {
			w.write(node.getLabel() + " ");
			w.write(node.getSplitCriteria() + "\n");
			count++;
			count += writeContextTreeNode(w, left);
			count += writeContextTreeNode(w, right);
		} else {
			w.write(node.getLabel() + " ");
			w.write("-1 -1 \n");
			count++;
		}
		return count;
	}
	
	/**
	 * Constructor for subclasses.
	 * @param ccdFile
	 */
	protected Optimizer(String ccdFile) {
		contextData = new ContextDataCollection();
		ContextDefinition.setCCDFile(ccdFile);
	}
	
	/**
	 * Recursively prints contents of context tree nodes.  For debug.
	 * @param node
	 */
	protected void dumpContextTree(ContextTreeNode node) {
                dumpContextTree(node, 0);
	}

	/**
	 * Recursively prints contents of context tree nodes.  For debug.
	 * @param node
	 */
	protected void dumpContextTree(ContextTreeNode node, int level) {
                
		ContextTreeNode left = node.getLeftChild();
		ContextTreeNode right = node.getRightChild();
		if (left != null) {
			dumpContextTree(left,level+1);
		}
                System.out.print("level:");
                if (level < 10) System.out.print(" ");
                System.out.print(level+" ");
  		System.out.println(node);
		if (right != null) {
			dumpContextTree(right,level+1);
		}
	}


	/**
	 * Recursively prints contents of context tree nodes.  For debug.
	 * @param node
	 */
	protected void dumpContextTreeSplits(ContextTreeNode node, int level) {
                
		ContextTreeNode left = node.getLeftChild();
		ContextTreeNode right = node.getRightChild();
                for (int i=0; i < level*2; i++) System.out.print(" ");
                if (node.getSplitCriteria() != null) {
                    System.out.println("split: " + node.getSplitCriteria());
                }
                else {
                    System.out.println("count: " + node.getCount());
                }
		if (left != null) {
			dumpContextTreeSplits(left,level+1);
		}
		if (right != null) {
			dumpContextTreeSplits(right,level+1);
		}
	}
	
	/**
	 * Loads context characteristics data from a context characteristics
	 * data file.
	 *  if ccFile = "-" then load ccFile from stdin; assumes
         *   stdin is in txt2bytes format.  
	 * @param ccFile context characteristics data file name.
	 */
	public void loadContextData(String ccFile) {
		
		// read cc data file and parse it
		InputStream bufread = null;
		ProcessBuilder pb= new ProcessBuilder("txt2bytes", ccFile);
		try {
		    byte nextbyte;
                    if (ccFile.equals("-")) { // read from stdin. 
                      bufread = System.in; 
                    }
                    else {                    
		       Process p = pb.start();
		       bufread = new BufferedInputStream( p.getInputStream());
                    }

			int count = 0;
			int numCtx = ContextDefinition.getContextDefinition().getNumContexts();
			int next;
			
			while ( (next = bufread.read())!=-1) {		
			    nextbyte = (byte) next;
				    
				// keep track of number of data
				count++;
				//                                if (count%100==0) System.out.print(".");
				// build up a new context characteristics
				ContextCharacteristics cc = new ContextCharacteristics();
				
				// read input items
				int bitval = nextbyte;
				
				// set bucket indexes for each context
				for (int ctxid=0; ctxid<numCtx; ctxid++) {
					// read next context value
				    next = bufread.read();
				    if (next == -1) 
					throw new RuntimeException("End of file in the middle of a context characteristic!");
				    nextbyte = (byte) next;
				    int ctxval = nextbyte;
					
					// find the bucket id corresponding to the context value
					Context ctx = ContextDefinition.getContextDefinition().getContext(ctxid);
					int bucketID = ctx.getBucketID(ctxval);
					
					// System.out.println(count + ": ctx=" + ctx + ",val=" + ctxval + ",bucket=" + bucketID);
					
					// store the bucket id in the context characteristics
					cc.setBucketID(ctxid, bucketID);
				}
				
				// System.out.println(count + ": " + cc.toString());
				
				// add bit value count for the context characteristics
				if (bitval == 0) {
					contextData.addBitCount(cc, 1, 0);
				} else if (bitval == 1) {
					contextData.addBitCount(cc, 0, 1);
				} else {
					throw new RuntimeException("Invalid bit value=" + bitval);
				}
			}

			if (DEBUG) {
				System.out.println("Number of data lines: " + count);
				System.out.println("Number of distinct context characteristics: " + contextData.size());
				System.out.println("Number possible different context characteristisc: " 
						   + (ContextDefinition.getContextDefinition()).maxPossibleDifferentContextChars());

				// list bit value distribution for each context 
                                contextData.printBitDistributionStats();
			}
			
		} catch (IOException ex) {
			System.out.println(ex.getMessage());
		} finally {
			if (bufread != null) try {bufread.close(); } catch (Exception ex){}
		}	
	}
	
	/**
	 * Finds the optimal context tree for given context data collection.
	 * 
	 * @param data context characteristics data collection.
	 * @param threshold cost-savings threshold
	 * @return
	 */
	public abstract ContextTreeNode findOptimalContextTree(double threshold);
	
	/**
	 * Labels the context tree nodes in in-order order.
	 * 
	 * @param tree context tree.
	 * @order order of the node
	 */
	public void labelContextTree(ContextTreeNode tree) {
		labelContextTreeNode(tree, 1);
		if (FULLDEBUG) {
			System.out.println("Context tree labeled->");
			dumpContextTree(tree);
		}
	}

	/**
	 * Saves context tree contents to a context tree description file.
	 * 
	 * @param ctdFile context tree description file name.
	 */
	public void saveContextTree(ContextTreeNode tree, String ctdFile) {
                if (DEBUG) 
                    tree.printCriteriaUsageStats();
		BufferedWriter bufwrite = null;
		try {
			// write nodes
			bufwrite = new BufferedWriter(new FileWriter(ctdFile));
			int count = writeContextTreeNode(bufwrite, tree);
			bufwrite.flush();
			
			// report progress
			System.out.println("finished writing " + count + " context characteristics tree nodes...");
			
		} catch (IOException ex) {
			System.out.println(ex.getMessage());
		} finally {
			if (bufwrite != null) try {bufwrite.close(); } catch (Exception ex){}
		}			
	}
}
